
class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

/**
 * 25. K 个一组翻转链表
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
 */
class Solution {
   public ListNode reverseKGroup(ListNode head, int k) {
       //1、先求出需要逆序多少组
       int n = 0;
       ListNode cur = head;
       while(cur != null) {
           n++;
           cur = cur.next;
       }
       n /= k;
       //2、重复 n 次：长度为k的链表逆序
       ListNode newHead = new ListNode(0);
       ListNode prev = newHead;
       cur = head;
       for(int i = 0; i < n; i++) {
           ListNode tmp = cur;
           for(int j = 0; j < k; j++) {
               //头插
               ListNode next = cur.next;
               cur.next = prev.next;
               prev.next = cur;
               cur = next;
           }
           prev = tmp;
       }
       //把后面不需要逆序的部分连接上
       prev.next = cur;
       return newHead.next;
   }
}